package com.zjsru.leetcode75.level1.chian;

/**
 * @Author: cookLee
 * @Date: 2023-12-10
 */
public class DeleteMiddle {

    /**
     * 主
     * \
     * 输入：head = [1,3,4,7,1,2,6]
     * 输出：[1,3,4,1,2,6]
     * 解释：
     * 上图表示给出的链表。节点的下标分别标注在每个节点的下方。
     * 由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
     * 返回结果为移除节点后的新链表。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        DeleteMiddle deleteMiddle = new DeleteMiddle();
        System.out.println(deleteMiddle.deleteMiddle(head));
    }

    /**
     * 删除中间
     *
     * @param head 封头
     * @return {@link ListNode}
     */
    public ListNode deleteMiddle(ListNode head) {
        //处理头节点，使他为0，方便后续快慢指针操作
        ListNode header = new ListNode(0, head);
        ListNode p1 = header;
        ListNode p2 = header.next;
        //p1 每次移动一步，而 p2 每次移动两步，直到 p2 到达链表末尾,当 p2 到达末尾时，p1 正好指向链表的中间节点的前一个节点
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        //将中间节点的前一个节点 p1 的 next 指针跳过中间节点，直接指向中间节点的下一个节点，从而删除了中间节点。
        p1.next = p1.next.next;
        return header.next;
    }




}
